package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.Stack;

/**
 * @author zhangjy
 * @description 相同的树
 * @date 2025/4/16 9:45
 */
public class IsSameTree_100 {

    /**
     * 个解：dfs-迭代-参考dmsxl
     */
    public boolean isSameTree3(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(p);
        stack.push(q);
        while (!stack.isEmpty()) {

            // 先弹出q，后弹出p
            TreeNode pPop = stack.pop();
            TreeNode qPop = stack.pop();

            // 都空
            // 表明其两个父节点是叶子节点，两个父节点相同。但不能return true，说明p、q两棵树相同，需要遍历完所有节点才能证明p、q相同。所以要继续continue
            if (pPop == null && qPop == null) continue;
            // pPop空，qPop非空
            if (pPop == null) return false;
            // pPop非空，qPop空
            if (qPop == null) return false;
            // 都非空，且节点值不同
            if (pPop.val != qPop.val) return false;

            // 都非空且节点值相同，继续向下迭代
            // 空也入栈，这样才能判断结构
            stack.push(pPop.left);
            stack.push(qPop.left);
            stack.push(pPop.right);
            stack.push(qPop.right);

        }

        return true;
    }

    /**
     * 个解：bfs-迭代-层序
     * <p>
     * 思路：
     * 层序遍历时，每层遍历次数要除以2，否则栈空后还在pop()，因为每次会同时会入栈两个节点。
     */
    public boolean isSameTree2(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(p);
        stack.push(q);
        while (!stack.isEmpty()) {
            int levelSize = stack.size();
            for (int i = 0; i < levelSize / 2; i++) {
                // 先弹出q，后弹出p
                TreeNode pPop = stack.pop();
                TreeNode qPop = stack.pop();

                // 都空
                // 表明其两个父节点是叶子节点，两个父节点相同。但不能return true，说明p、q两棵树相同，需要遍历完所有节点才能证明p、q相同。所以要继续continue
                if (pPop == null && qPop == null) continue;
                // pPop空，qPop非空
                if (pPop == null) return false;
                // pPop非空，qPop空
                if (qPop == null) return false;
                // 都非空，且节点值不同
                if (pPop.val != qPop.val) return false;

                // 都非空且节点值相同，继续向下迭代
                // 空也入栈，这样才能判断结构
                stack.push(pPop.left);
                stack.push(qPop.left);
                stack.push(pPop.right);
                stack.push(qPop.right);
            }
        }

        return true;
    }

    /**
     * 个解：dfs-递归-后序
     * <p>
     * 分析：
     * 要判断两棵树是否相同（结构和节点值都相同）——>判断同一层对应孩子是否相同——>要先判断孩子，就考虑后序
     * <p>
     * T(n) = O(n)；其中，n是p、q的节点总数，每个节点只判断一次。
     * S(n) = O(n)；其中，
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // p、q都空
        if (p == null && q == null) return true;
        // p空，q非空
        if (p == null) return false;
        // p非空，q空
        if (q == null) return false;
        // p、q都非空，且节点值不同
        if (p.val != q.val) return false;

        // 走到这里，一定有p、q非空且节点值相同（满足结构、节点值都相同）
        // 左
        boolean left = isSameTree(p.left, q.left);
        // 右
        boolean right = isSameTree(p.right, q.right);
        // 中
        return left && right;
    }

}
